﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0088_Jump : IAlgorithm
    {
        // 45. 跳跃游戏 II

        // 给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
        // 数组中的每个元素代表你在该位置可以跳跃的最大长度。
        // 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
        // 假设你总是可以到达数组的最后一个位置。

        // 提示:
        //  1 <= nums.length <= 10^4
        //  0 <= nums[i] <= 1000

        public void Test()
        {
            // 算法参数定义
            var nums = new int[] { 2, 3, 0, 1, 4 };
            // 算法执行与打印
            Console.WriteLine(Jump(nums));
        }

        // 算法
        public int Jump(int[] nums)
        {
            var dp = new int[nums.Length];
            for (int i = 0; i < nums.Length - 1; i++)
                for (int j = i + 1; j <= nums[i] + i && j < nums.Length; j++)
                    dp[j] = dp[j] == 0 ? dp[i] + 1 : Math.Min(dp[j], dp[i] + 1);
            return dp[nums.Length - 1];
        }

        public int Jump1(int[] nums)
        {
            int end = 0, maxPosition = 0, steps = 0;
            for (int i = 0; i < nums.Length - 1; i++)
            {
                maxPosition = Math.Max(maxPosition, i + nums[i]);
                if (i == end)
                {
                    end = maxPosition;
                    steps++;
                }
            }
            return steps;
        }
    }
}
